home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_high.lha / LEDA-3.1c-high / man / sortseq.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  6.9 KB  |  156 lines
  1. {\magonebf 4.6 Sorted Sequences  (sortseq)}
  2.  
  3. \decltwo sortseq K I 
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $S$ of the parameterized data type \name\ is a sequence of
  8. items ($seq\_item$). Every item contains a key from the linearly ordered data 
  9. type $K$, called the key type of $S$, and an information from data type $I$,
  10. called the information type  of $S$. The number of items in $S$ is called the 
  11. size of $S$. A sorted sequence of size zero is called empty. We use $<k,i>$ to 
  12. denote a $seq\_item$ with key $k$ and information $i$ (called the information 
  13. associated with key $k$). For each $k \in K$ there is at most one item 
  14. $<k,i> \in S$. 
  15.  
  16. The linear order on $K$ may be time-dependent, e.g., in an algorithm that
  17. sweeps an arrangement of lines by a vertical sweep line we may want to order
  18. the lines by the y-coordinates of their intersections with the sweep line. 
  19. However, whenever an operation (except of reverse\_items) is applied to a 
  20. sorted sequence $S$, the keys of $S$ must form an increasing sequence according
  21. to the currently valid linear order on $K$. For operation reverse\_items this 
  22. must hold after the execution of the operation.
  23.  
  24. \bigskip
  25. {\bf 2. Creation}
  26.  
  27. a) \create S {}
  28.  
  29. b) $\_sortseq${\tt <}$K,I,seq\_impl${\tt >} $S$ ;
  30.  
  31. creates an instance \var\ of type \name\ and initializes it to the empty 
  32. sorted sequence. Variant a) chooses the default data structure
  33. (cf.~4.6.4), and variant b) chooses class $seq\_impl$ as the 
  34. implementation of the sorted sequence (cf.~section~9 for a list of possible
  35. implementation parameters).
  36.  
  37.  
  38.  
  39. \bigskip
  40. {\bf 3. Operations}
  41.  
  42. \+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
  43. \smallskip
  44. \+\op K         key         {seq\_item\ it}     
  45.                                {returns the key of item $it$}
  46. \+\nop                         {\precond $it$ is an item in \var.}
  47. \smallskip
  48. \+\op I         inf         {seq\_item\ it}     
  49.                                {returns the information of item $it$}
  50. \+\nop                         {\precond $it$ is an item in \var.}
  51. \smallskip
  52. \+\op seq\_item lookup      {K\ k}    
  53.                                {returns the item with key $k$ }
  54. \+\nop                         {( nil if no such item exists in \var\ )}
  55. \smallskip
  56. \vfill\eject
  57.  
  58. \+\op seq\_item insert      {K\ k, I\ i}
  59.                                {associates information $i$ with key $k$: If}
  60. \+\nop                         {there is an item $<k,j>$ in \var\ then $j$ is}
  61. \+\nop                         {replaced by $i$, else a new item $<k,i>$ is}
  62. \+\nop                         {added to \var. In both cases the item is }
  63. \+\nop                         {returned.}
  64. \smallskip
  65. \+\op seq\_item insert\_at  {seq\_item\ it,\ K\ k, I\ i} {}
  66. \+\nop                         {Like insert($k,i$), the item $it$ gives the}
  67. \+\nop                         {position of the item $<k,i>$ in the sequence}
  68. \+\nop                         {\precond $it$ is an item in $S$ with either}
  69. \+\nop                         {key($it$) is maximal with key($it) < k$ or}
  70. \+\nop                         {key($it$) is minimal with key$(it) > k$}
  71. \smallskip
  72. \+\op seq\_item locate      {K\ k}    
  73.                                {returns the item $<k\',i>$ in \var\ such that}
  74. \+\nop                         {$k\'$ is minimal with $k\' >= k$ ( nil if no }
  75. \+\nop                         {such item exists).}
  76. \smallskip
  77. \+\op seq\_item locate\_pred {K\ k}    
  78.                                {returns the item $<k\',i>$ in \var\ such that}
  79. \+\nop                         {$k\'$ is maximal with $k\' <= k$ ( nil if no }
  80. \+\nop                         {such item exists).}
  81. \smallskip
  82. \+\op seq\_item succ        {seq\_item\ it}      
  83.                               {returns the successor item of it, i.e., the }
  84. \+\nop                        {item $<k,i>$ in \var\ such that $k$ is minimal}
  85. \+\nop                        {with $k > key(it)$ (nil if no such item exists).}
  86. \+\nop                        {\precond $it$ is an item in \var.}
  87. \smallskip 
  88. \+\op seq\_item pred        {seq\_item\ it}      
  89.                               {returns the predecessor item of $it$, i.e., the}
  90. \+\nop                        {item $<k,i>$ in \var\ such that $k$ is maximal }
  91. \+\nop                        {with $k < key(it)$ (nil if no such item exists).}
  92. \+\nop                        {\precond $it$ is an item in \var.}
  93. \smallskip
  94. \+\op seq\_item max         {}       
  95.                                {returns the item with maximal key}
  96. \+\nop                         {(nil if \var\ is empty).}
  97. \smallskip
  98. \+\op seq\_item min         {}       
  99.                                {returns the item with minimal key}
  100. \+\nop                         {(nil if \var\ is empty).}
  101. \smallskip
  102. \+\op void      del\_item   {seq\_item\ it}    
  103.                                {removes the item $it$ from \var.}
  104. \+\nop                         {\precond $it$ is an item in \var.}
  105. \smallskip
  106. \+\op void      del         {K\ k}    
  107.                                {removes the item with key $k$ from \var}
  108. \+\nop                         {(null operation if no such item exists).}
  109. \smallskip
  110. \+\op void      change\_inf {seq\_item\ it,\ I\ i} 
  111.                                {makes $i$ the information of item $it$.}
  112. \+\nop                         {\precond $it$ is an item in \var.}
  113. \smallskip
  114. \+\op void      reverse\_items {seq\_item\ a,\ seq\_item\ b}  {}
  115. \+\nop                     {the subsequence of $S$ from $a$ to $b$ is reversed.}
  116. \+\nop                     {\precond $a$ appears before $b$ in $S$.}
  117. \smallskip
  118. \+\op void      split {seq\_item\ it,\ sortseq<K,I>\&\ S_1,\ sortseq<K,I>\&\ S_2}  {}
  119. \+\nop                {splits $S$ at item $it$ into sequences $S_1$ and $S_2$}
  120. \+\nop                {and makes $S$ empty. More precisely, if}
  121. \+\nop                {$S = x_1,\dots,x_{k-1},it,x_{k+1},\dots,x_n$ then}
  122. \+\nop                {$S1 = x_1,\dots,x_{k-1},it$ and $S2 = x_{k+1},\dots,x_n$}
  123. \+\nop                {\precond $it$ is an item in $S$. }
  124. \smallskip
  125. \+\op sortseq<K,I>\& conc {sortseq<K,I>\&\ S_1} 
  126.                      {appends $S_1$ to $S$, makes $S_1$ empty and} 
  127. \+\nop               {returns $S$. \precond }
  128. \+\nop               {$S$.key($S$.max()) $\le$ $S_1$.key($S_1$.min()).}
  129. \smallskip
  130. \+\op void      clear       {}       
  131.                                {makes \var\ the empty sorted sequence.}
  132. \smallskip
  133. \+\op int       size        {}       
  134.                                {returns the size of \var.}
  135. \smallskip
  136. \+\op bool      empty       {}       
  137.                               {returns true if \var\ is empty, false otherwise.}
  138.  
  139.  
  140. \bigskip
  141. {\bf 4. Implementation}
  142. \medskip
  143. Sorted sequences are implemented by (2,4)-trees. Operations lookup, locate, 
  144. insert, del, split, conc take time $O(\log n)$, operations succ, pred, max, 
  145. min, key, inf, insert\_at\_item and del\_item take time $O(1)$. Clear takes 
  146. time $O(n)$ and reverse\_items $O(\ell)$, where $\ell$ is the length of the 
  147. reversed subsequence. The space requirement is $O(n)$. Here $n$ is the current 
  148. size of the sequence.
  149.  
  150.  
  151. \bigskip
  152. {\bf 5. Example }
  153. \medskip
  154. \input prog/sortseq.prog
  155.  
  156.